\batchmode
\makeatletter
\def\input@path{{/Users/sergei.winitzki/Code/talks/ftt-fp/}}
\makeatother
\documentclass[english]{beamer}
\usepackage[T1]{fontenc}
\usepackage[latin9]{inputenc}
\setcounter{secnumdepth}{3}
\setcounter{tocdepth}{3}
\usepackage{babel}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage[all]{xy}
\ifx\hypersetup\undefined
  \AtBeginDocument{%
    \hypersetup{unicode=true,pdfusetitle,
 bookmarks=true,bookmarksnumbered=false,bookmarksopen=false,
 breaklinks=false,pdfborder={0 0 1},backref=false,colorlinks=true}
  }
\else
  \hypersetup{unicode=true,pdfusetitle,
 bookmarks=true,bookmarksnumbered=false,bookmarksopen=false,
 breaklinks=false,pdfborder={0 0 1},backref=false,colorlinks=true}
\fi

\makeatletter

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% LyX specific LaTeX commands.
%% Because html converters don't know tabularnewline
\providecommand{\tabularnewline}{\\}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Textclass specific LaTeX commands.
% this default might be overridden by plain title style
\newcommand\makebeamertitle{\frame{\maketitle}}%
% (ERT) argument for the TOC
\AtBeginDocument{%
  \let\origtableofcontents=\tableofcontents
  \def\tableofcontents{\@ifnextchar[{\origtableofcontents}{\gobbletableofcontents}}
  \def\gobbletableofcontents#1{\origtableofcontents}
}
\newenvironment{lyxcode}
  {\par\begin{list}{}{
    \setlength{\rightmargin}{\leftmargin}
    \setlength{\listparindent}{0pt}% needed for AMS classes
    \raggedright
    \setlength{\itemsep}{0pt}
    \setlength{\parsep}{0pt}
    \normalfont\ttfamily}%
   \def\{{\char`\{}
   \def\}{\char`\}}
   \def\textasciitilde{\char`\~}
   \item[]}
  {\end{list}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% User specified LaTeX commands.
\usetheme[secheader]{Boadilla}
\usecolortheme{seahorse}
\title[Chapter 7: Functor-lifted computations II]{Chapter 7: Computations lifted to a functor context II. Monads}
\subtitle{Part 2: Laws and structure of monads and semimonads}
\author{Sergei Winitzki}
\date{2018-05-27}
\institute[ABTB]{Academy by the Bay}
\setbeamertemplate{headline}{} % disable headline at top
\setbeamertemplate{navigation symbols}{} % disable navigation bar at bottom
\usepackage[all]{xy}
\makeatletter
% Macros to assist LyX with XYpic when using scaling.
\newcommand{\xyScaleX}[1]{%
\makeatletter
\xydef@\xymatrixcolsep@{#1}
\makeatother
} % end of \xyScaleX
\makeatletter
\newcommand{\xyScaleY}[1]{%
\makeatletter
\xydef@\xymatrixrowsep@{#1}
\makeatother
} % end of \xyScaleY

\makeatother

\begin{document}
\frame{\titlepage}
\begin{frame}{Semimonad laws I: The intuitions}

What properties of functor block programs do we expect to have?
\begin{itemize}
\item In \texttt{\textcolor{blue}{\footnotesize{}x $\leftarrow$ c}}, the
value of \texttt{\textcolor{blue}{\footnotesize{}x}} will \emph{go
over items} held in container \texttt{\textcolor{blue}{\footnotesize{}c}} 
\item Manipulating items in container is followed by a generator:
\end{itemize}
\texttt{\textcolor{blue}{\footnotesize{}}}%
\begin{minipage}[c][1\totalheight][t]{0.49\columnwidth}%
\begin{lyxcode}
\textcolor{blue}{\footnotesize{}x~$\leftarrow$~cont1}{\footnotesize\par}

\textcolor{blue}{\footnotesize{}y~=~f(x)}{\footnotesize\par}

\textcolor{blue}{\footnotesize{}z~$\leftarrow$~cont2(y)}{\footnotesize\par}
\end{lyxcode}
%
\end{minipage}\texttt{\textcolor{blue}{\footnotesize{}\hfill{}}}%
\begin{minipage}[c][1\totalheight][t]{0.4\columnwidth}%
\begin{lyxcode}
\textcolor{blue}{\footnotesize{}y~$\leftarrow$~cont1}{\footnotesize\par}

\textcolor{blue}{\footnotesize{}~~~~~~.map(x~$\Rightarrow$~f(x))}{\footnotesize\par}

\textcolor{blue}{\footnotesize{}z~$\leftarrow$~cont2(y)}{\footnotesize\par}
\end{lyxcode}
%
\end{minipage}\texttt{\textcolor{blue}{\footnotesize{}\hfill{}\medskip{}
}}{\footnotesize\par}

\texttt{\textcolor{blue}{\footnotesize{}cont1.flatMap(x $\Rightarrow$
cont2(f(x))) = cont1.map(f).flatMap(y $\Rightarrow$ cont2(y))}} 
\begin{itemize}
\item Manipulating items in container is preceded by a generator:
\end{itemize}
\texttt{\textcolor{blue}{\footnotesize{}}}%
\begin{minipage}[c][1\totalheight][t]{0.49\columnwidth}%
\begin{lyxcode}
\textcolor{blue}{\footnotesize{}x~$\leftarrow$~cont1}{\footnotesize\par}

\textcolor{blue}{\footnotesize{}y~$\leftarrow$~cont2(x)}{\footnotesize\par}

\textcolor{blue}{\footnotesize{}z~=~f(y)}{\footnotesize\par}
\end{lyxcode}
%
\end{minipage}\texttt{\textcolor{blue}{\footnotesize{}\hfill{}}}%
\begin{minipage}[c][1\totalheight][t]{0.49\columnwidth}%
\begin{lyxcode}
\textcolor{blue}{\footnotesize{}x~$\leftarrow$~cont1}{\footnotesize\par}

\textcolor{blue}{\footnotesize{}z~$\leftarrow$~cont2(x)}{\footnotesize\par}

\textcolor{blue}{\footnotesize{}~~~~~~~.map(f)}{\footnotesize\par}
\end{lyxcode}
%
\end{minipage}\texttt{\textcolor{blue}{\footnotesize{}\hfill{}\medskip{}
cont1.flatMap(cont2).map(f)}} \texttt{\textcolor{blue}{\footnotesize{}=
cont1.flatMap(x $\Rightarrow$ cont2(x).map(f))}} 
\begin{itemize}
\item Within a generator, \texttt{\textcolor{blue}{\footnotesize{}for \{...\}
yield}} can be inlined:
\end{itemize}
\texttt{\textcolor{blue}{\footnotesize{}}}%
\begin{minipage}[c][1\totalheight][t]{0.49\columnwidth}%
\begin{lyxcode}
\textcolor{blue}{\footnotesize{}x~$\leftarrow$~cont}{\footnotesize\par}

\textcolor{blue}{\footnotesize{}y~$\leftarrow$~p(x)}{\footnotesize\par}

\textcolor{blue}{\footnotesize{}z~$\leftarrow$~cont2(y)}{\footnotesize\par}
\end{lyxcode}
%
\end{minipage}\texttt{\textcolor{blue}{\footnotesize{}\hfill{}}}%
\begin{minipage}[c][1\totalheight][t]{0.49\columnwidth}%
\begin{lyxcode}
\textcolor{blue}{\footnotesize{}yy~$\leftarrow$~for~\{~x~$\leftarrow$~cont}{\footnotesize\par}

\textcolor{blue}{\footnotesize{}~~~~~~~~~~~~y~$\leftarrow$~p(x)~\}~yield~y}{\footnotesize\par}

\textcolor{blue}{\footnotesize{}z~$\leftarrow$~cont2(yy)}{\footnotesize\par}
\end{lyxcode}
%
\end{minipage}\texttt{\textcolor{blue}{\footnotesize{}\hfill{}\medskip{}
cont.flatMap(x $\Rightarrow$ p(x).flatMap(cont2)) = cont.flatMap(p).flatMap(cont2)}} 
\end{frame}

\begin{frame}{Semimonad laws II: The laws for \texttt{\textcolor{blue}{\footnotesize{}flatMap}} }

For brevity, write {\footnotesize{}$\text{flm}$} instead of \texttt{\textcolor{blue}{\footnotesize{}flatMap}} 

A \textbf{semimonad} $S^{A}$ has {\footnotesize{}$\text{flm}^{\left[A,B\right]}:\left(A\Rightarrow S^{B}\right)\Rightarrow S^{A}\Rightarrow S^{B}$}
with 3 laws:
\begin{enumerate}
\item {\footnotesize{}$\text{flm}\,(f^{A\Rightarrow B}\circ g^{B\Rightarrow S^{C}})=\text{fmap}\,f\circ\text{flm}\,g$}
{\footnotesize{}(naturality in $A$)} {\footnotesize{}
\[
\xymatrix{\xyScaleY{0.2pc}\xyScaleX{3pc} & S^{B}\ar[rd]\sp(0.5){\ \text{flm}\,g^{B\Rightarrow S^{C}}}\\
S^{A}\ar[ru]\sp(0.5){\text{fmap}\,f^{A\Rightarrow B}\ }\ar[rr]\sb(0.5){\text{flm}\,(f^{A\Rightarrow B}\circ\,g^{B\Rightarrow S^{C}})\,} &  & S^{C}
}
\]
}{\footnotesize\par}
\item {\footnotesize{}$\text{flm}\,\big(f^{A\Rightarrow S^{B}}\circ\text{fmap}\,g^{B\Rightarrow C}\big)=\text{flm}\,f\circ\text{fmap}\,g$}
{\footnotesize{}(naturality in $B$)} {\footnotesize{}
\[
\xymatrix{\xyScaleY{0.2pc}\xyScaleX{3pc} & S^{B}\ar[rd]\sp(0.5){\ \text{fmap}\,g^{B\Rightarrow C}}\\
S^{A}\ar[ru]\sp(0.5){\text{flm}\,f^{A\Rightarrow S^{B}}\ }\ar[rr]\sb(0.5){\text{flm}\,(f^{A\Rightarrow S^{B}}\circ\,\text{fmap}\,g^{B\Rightarrow C})\,} &  & S^{C}
}
\]
}{\footnotesize\par}
\item {\footnotesize{}$\text{flm}\,\big(f^{A\Rightarrow S^{B}}\circ\text{flm}\,g^{B\Rightarrow S^{C}}\big)=\text{flm}\,f\circ\text{flm}\,g$}
{\footnotesize{}(associativity)} {\footnotesize{}
\[
\xymatrix{\xyScaleY{0.2pc}\xyScaleX{3pc} & S^{B}\ar[rd]\sp(0.5){\ \text{flm}\,g^{B\Rightarrow S^{C}}}\\
S^{A}\ar[ru]\sp(0.5){\text{flm}\,f^{A\Rightarrow S^{B}}\ }\ar[rr]\sb(0.5){\text{flm}\,\big(f^{A\Rightarrow S^{B}}\circ\,\text{flm}\,g^{B\Rightarrow S^{C}}\big)\,} &  & S^{C}
}
\]
}{\footnotesize\par}
\end{enumerate}
Is there a shorter and clearer formulation of these laws?
\end{frame}

\begin{frame}{Semimonad laws III: The laws for \texttt{\textcolor{blue}{\footnotesize{}flatten}} }

The methods \texttt{\textcolor{blue}{\footnotesize{}flatten}} (denoted
by {\footnotesize{}$\text{ftn}$}) and \texttt{\textcolor{blue}{\footnotesize{}flatMap}}
are equivalent:\texttt{\textcolor{blue}{\footnotesize{} }}%
\begin{minipage}[c][1\totalheight][t]{0.4\columnwidth}%
{\footnotesize{}
\begin{align*}
\text{ftn}^{\left[A\right]}:S^{S^{A}}\Rightarrow S^{A} & \equiv\text{flm}^{\left[S^{A},A\right]}(m^{S^{A}}\Rightarrow m)\\
\text{flm}\,\big(f^{A\Rightarrow S^{B}}\big) & \equiv\text{fmap}\,f\circ\text{ftn}
\end{align*}
}%
\end{minipage}\texttt{\textcolor{blue}{\footnotesize{}\hfill{}}}%
\begin{minipage}[c][1\totalheight][t]{0.4\columnwidth}%
{\footnotesize{}
\[
\xymatrix{\xyScaleY{0.2pc}\xyScaleX{3pc} & S^{S^{B}}\ar[rd]\sp(0.5){\ \text{ftn}\ }\\
S^{A}\ar[ru]\sp(0.5){\text{fmap}\,f^{A\Rightarrow S^{B}}\ }\ar[rr]\sb(0.5){\text{flm}\,\big(f^{A\Rightarrow S^{B}}\big)\,} &  & S^{B}
}
\]
}%
\end{minipage}\texttt{\textcolor{blue}{\footnotesize{}\  \  \ \hfill{}}}{\footnotesize\par}

It turns out that \texttt{\textcolor{blue}{\footnotesize{}flatten}}
has only 2 laws:
\begin{enumerate}
\item {\footnotesize{}$\text{fmap}\big(\text{fmap}\,f^{A\Rightarrow B}\big)\circ\text{ftn}^{\left[B\right]}=\text{ftn}^{\left[A\right]}\circ\text{fmap}\,f$}
{\footnotesize{}(naturality)
\[
\xymatrix{\xyScaleY{0.2pc}\xyScaleX{5pc} & S^{S^{B}}\ar[rd]\sp(0.5){\ \text{ftn}^{\left[B\right]}}\\
S^{S^{A}}\ar[ru]\sp(0.5){\text{fmap}\,\big(\text{fmap}\,f^{A\Rightarrow B}\big)\ \ }\ar[rd]\sb(0.5){\text{ftn}^{\left[A\right]}\,} &  & S^{B}\\
 & S^{A}\ar[ru]\sb(0.5){\text{fmap}\,f^{A\Rightarrow B}}
}
\]
}{\footnotesize\par}
\item {\footnotesize{}$\text{fmap}\,(\text{ftn}^{\left[A\right]})\circ\text{ftn}^{\left[A\right]}=\text{ftn}^{[S^{A}]}\circ\text{ftn}^{\left[A\right]}$}
{\footnotesize{}(associativity) 
\[
\xymatrix{\xyScaleY{0.2pc}\xyScaleX{5pc} & S^{S^{A}}\ar[rd]\sp(0.5){\ \text{ftn}^{\left[A\right]}}\\
S^{S^{S^{A}}}\ar[ru]\sp(0.5){\text{fmap}\,(\text{ftn}^{\left[A\right]})\ }\ar[rd]\sb(0.5){\text{ftn}^{[S^{A}]}\,} &  & S^{A}\\
 & S^{S^{A}}\ar[ru]\sb(0.5){\text{ftn}^{\left[A\right]}}
}
\]
}{\footnotesize\par}
\end{enumerate}
\end{frame}

\begin{frame}{Equivalence of a natural transformation and a ``lifting''}
\begin{itemize}
\item Equivalence of {\footnotesize{}$\text{flm}$} and {\footnotesize{}$\text{ftn}$}:
{\footnotesize{}$\text{ftn}=\text{flm}\left(\text{id}\right)$; $\text{flm}\,f=\text{fmap}\,f\circ\text{ftn}$} 
\item We saw this before: {\footnotesize{}$\text{deflate}=\text{fmapOpt}\left(\text{id}\right)$};
{\footnotesize{}$\text{fmapOpt}\,f=\text{fmap}\:f\circ\text{deflate}$} 
\begin{itemize}
\item Is there a general pattern where two such functions are equivalent?
\end{itemize}
\item Let {\footnotesize{}$\text{tr}:F^{G^{A}}\Rightarrow F^{A}$ }be a
natural transformation ($F$ and $G$ are functors)
\item Define {\footnotesize{}$\text{ftr}:\left(A\Rightarrow G^{B}\right)\Rightarrow F^{A}\Rightarrow F^{B}$}
by {\footnotesize{}$\text{ftr}\,f=\text{fmap}\,f\circ\text{tr}$} 
\item It follows that {\footnotesize{}$\text{tr}=\text{ftr}\left(\text{id}\right)$},
and we have equivalence between {\footnotesize{}$\text{tr}$} and
{\footnotesize{}$\text{ftr}$}:\texttt{\textcolor{blue}{\footnotesize{} }}%
\begin{minipage}[c][1\totalheight][t]{0.4\columnwidth}%
{\footnotesize{}
\begin{align*}
\text{tr}:F^{G^{A}}\Rightarrow F^{A} & =\text{ftr}(m^{G^{A}}\Rightarrow m)\\
\text{ftr}\,\big(f^{A\Rightarrow G^{B}}\big) & =\text{fmap}\,f\circ\text{tr}
\end{align*}
}%
\end{minipage}\texttt{\textcolor{blue}{\footnotesize{}\hfill{}}}%
\begin{minipage}[c][1\totalheight][t]{0.4\columnwidth}%
{\footnotesize{}
\[
\xymatrix{\xyScaleY{0.2pc}\xyScaleX{3pc} & F^{G^{B}}\ar[rd]\sp(0.5){\ \text{tr}\ }\\
F^{A}\ar[ru]\sp(0.5){\text{fmap}\,f^{A\Rightarrow G^{B}}\ }\ar[rr]\sb(0.5){\text{ftr}\,\big(f^{A\Rightarrow G^{B}}\big)\,} &  & F^{B}
}
\]
}%
\end{minipage}\texttt{\textcolor{blue}{\footnotesize{}\  \  \ \hfill{}}}{\footnotesize\par}
\item An automatic law for {\footnotesize{}$\text{ftr}$} (``naturality
in $A$'') follows from the definition: {\footnotesize{}$\text{fmap}\,g\circ\text{ftr}\,f=\text{fmap}\,g\circ\text{fmap}\,f\circ\text{tr}=\text{fmap}\left(g\circ f\right)\circ\text{tr}=\text{ftr}\left(g\circ f\right)$} 
\begin{itemize}
\item This is why {\footnotesize{}$\text{tr}$} always has \emph{one law
fewer} than {\footnotesize{}$\text{ftr}$}{\footnotesize\par}
\end{itemize}
\item To demonstrate equivalence in the direction {\footnotesize{}$\text{ftr}\rightarrow\text{tr}$}:
Start with an arbitrary {\footnotesize{}$\text{ftr}$} satisfying
``naturality in $A$'', then obtain {\footnotesize{}$\text{tr}=\text{ftr}\left(\text{id}\right)$}
from it, then verify {\footnotesize{}$\text{ftr}\,f=\text{fmap}\,f\circ\text{tr}$}
with that {\footnotesize{}$\text{tr}$}; {\footnotesize{}$\text{fmap}\,f\circ\text{ftr}\left(\text{id}\right)=\text{ftr}\left(f\circ id\right)=\text{ftr}\,f$}{\footnotesize\par}
\end{itemize}
\end{frame}

\begin{frame}{Semimonad laws IV: Deriving the laws for \texttt{\textcolor{blue}{\footnotesize{}flatten}} }

Denote for brevity $q^{\uparrow}\equiv\text{fmap}\,q$ for any function
$q$ (``lifting'' $q^{A\Rightarrow B}$ to $S$)

Express $\text{flm}\,f=f^{\uparrow}\circ\text{ftn}$ and substitute
that into $\text{flm}$'s 3 laws:
\begin{enumerate}
\item {\footnotesize{}$\text{flm}\left(f\circ g\right)=f^{\uparrow}\circ\text{flm}\,g$}
gives {\footnotesize{}$\left(f\circ g\right)^{\uparrow}\circ\text{ftn}=f^{\uparrow}\circ g^{\uparrow}\circ\text{ftn}$}\\
-- this law holds automatically due to functor composition law
\item {\footnotesize{}$\text{flm}\left(f\circ g^{\uparrow}\right)=\text{flm}\,f\circ g^{\uparrow}$}
gives {\footnotesize{}$\left(f\circ g^{\uparrow}\right)^{\uparrow}\circ\text{ftn}=f^{\uparrow}\circ\text{ftn}\circ g^{\uparrow}$};\\
using the functor composition law, we reduce this to\\
{\footnotesize{}$g^{\uparrow\uparrow}\circ\text{ftn}=\text{ftn}\circ g^{\uparrow}$}
-- this is the naturality law
\item {\footnotesize{}$\text{flm}\left(f\circ\text{flm}\,g\right)=\text{flm}\,f\circ\text{flm}\,g$
}with functor composition law gives{\footnotesize{} $f^{\uparrow}\circ g^{\uparrow\uparrow}\circ\text{ftn}^{\uparrow}\circ\text{ftn}=f^{\uparrow}\circ\text{ftn}\circ g^{\uparrow}\circ\text{ftn}$;}
using {\footnotesize{}$\text{ftn}$}'s naturality and omitting the
common factor{\footnotesize{} $f^{\uparrow}\circ g^{\uparrow\uparrow}$},
we get{\footnotesize{} $\text{ftn}^{\uparrow}\circ\text{ftn}=\text{ftn}\circ\text{ftn}$}
-- associativity law
\end{enumerate}
\begin{itemize}
\item \texttt{\textcolor{blue}{\footnotesize{}flatten}} has the simplest
type signature \emph{and} the fewest laws
\item It is usually easy to check naturality!
\begin{itemize}
\item \textbf{Parametricity theorem}: Any \emph{pure, fully parametric}
code for a function of type $F^{A}\Rightarrow G^{A}$ will implement
a natural transformation
\end{itemize}
\item Checking \texttt{\textcolor{blue}{\footnotesize{}flatten}}'s associativity
needs \emph{a lot} more work!
\end{itemize}
The \texttt{\textcolor{blue}{\footnotesize{}cats}} library has a \texttt{\textcolor{blue}{\footnotesize{}FlatMap}}
type class, defining \texttt{\textcolor{blue}{\footnotesize{}flatten}}
via \texttt{\textcolor{blue}{\footnotesize{}flatMap}} 
\end{frame}

\begin{frame}{Checking the associativity law for standard monads}
\begin{itemize}
\item Implement \texttt{\textcolor{blue}{\footnotesize{}flatten}} for these
functors and check the laws (see code):
\begin{itemize}
\item \texttt{\textcolor{blue}{\footnotesize{}Option}} monad: $F^{A}\equiv1+A$;
$\text{ftn}:1+\left(1+A\right)\Rightarrow1+A$
\item \texttt{\textcolor{blue}{\footnotesize{}Either}} monad: $F^{A}\equiv Z+A$;
$\text{ftn}:Z+\left(Z+A\right)\Rightarrow Z+A$
\item \texttt{\textcolor{blue}{\footnotesize{}List}} monad: $F^{A}\equiv\text{List}^{A}$;
$\text{ftn}:\text{List}^{\text{List}^{A}}\Rightarrow\text{List}^{A}$
\item Writer monad: $F^{A}\equiv A\times W$; $\text{ftn}:\left(A\times W\right)\times W\Rightarrow A\times W$
\item Reader monad: $F^{A}\equiv R\Rightarrow A$; $\text{ftn}:\left(R\Rightarrow\left(R\Rightarrow A\right)\right)\Rightarrow R\Rightarrow A$
\item State: $F^{A}\equiv S\Rightarrow A\times S$; $\text{ftn}:\left(S\Rightarrow\left(S\Rightarrow A\times S\right)\times S\right)\Rightarrow S\Rightarrow A\times S$
\item Continuation monad: $F^{A}\equiv\left(A\Rightarrow R\right)\Rightarrow R$;
$\text{ftn}:\left(\left(\left(\left(A\Rightarrow R\right)\Rightarrow R\right)\Rightarrow R\right)\Rightarrow R\right)\Rightarrow\left(A\Rightarrow R\right)\Rightarrow R$
\end{itemize}
\item Code implementing these \texttt{\textcolor{blue}{\footnotesize{}flatten}}
functions is \emph{fully parametric} in $A$
\begin{itemize}
\item Naturality of these functions follows from parametricity theorem
\item Associativity needs to be checked for each monad!
\end{itemize}
\item Example of a useful semimonad that is \emph{not} a full monad:
\begin{itemize}
\item $F^{A}\equiv A\times V\times W$; $\text{ftn}\left(\left(a\times v_{1}\times w_{1}\right)\times v_{2}\times w_{2}\right)=a\times v_{1}\times w_{2}$
\end{itemize}
\item Examples of \emph{non-associative} (i.e.\ wrong) implementations
of \texttt{\textcolor{blue}{\footnotesize{}flatten}}:
\begin{itemize}
\item $F^{A}\equiv A\times W\times W$; $\text{ftn}\left(\left(a\times v_{1}\times v_{2}\right)\times w_{1}\times w_{2}\right)=a\times w_{2}\times w_{1}$
\item $F^{A}\equiv\text{List}^{A}$, but \texttt{\textcolor{blue}{\footnotesize{}flatten}}
concatenates the nested lists in reverse order
\end{itemize}
\end{itemize}
\end{frame}

\begin{frame}{Motivation for monads}

\begin{itemize}
\item Monads represent values with a ``special computational context''
\item Specific monads will have methods to create various contexts
\item Monadic composition will ``combine'' the contexts associatively
\item It is generally useful to have an ``empty context'' available:
\[
\text{pure}:A\Rightarrow M^{A}
\]
\end{itemize}
Adding the empty context to another context should be a no-op
\begin{itemize}
\item Empty context is followed by a generator:
\end{itemize}
\texttt{\textcolor{blue}{\footnotesize{}}}%
\begin{minipage}[c][1\totalheight][t]{0.49\columnwidth}%
\begin{lyxcode}
\textcolor{blue}{\footnotesize{}y~$\leftarrow$~pure(x)}{\footnotesize\par}

\textcolor{blue}{\footnotesize{}z~$\leftarrow$~cont(y)}{\footnotesize\par}
\end{lyxcode}
%
\end{minipage}\texttt{\textcolor{blue}{\footnotesize{}\hfill{}}}%
\begin{minipage}[c][1\totalheight][t]{0.4\columnwidth}%
\begin{lyxcode}
\textcolor{blue}{\footnotesize{}y~=~x}{\footnotesize\par}

\textcolor{blue}{\footnotesize{}z~$\leftarrow$~cont(y)}{\footnotesize\par}
\end{lyxcode}
%
\end{minipage}\texttt{\textcolor{blue}{\footnotesize{}\hfill{}\medskip{}
}}{\footnotesize\par}

\texttt{\textcolor{blue}{\footnotesize{}pure(x).flatMap(y $\Rightarrow$
cont(y)) = cont(x)}}$\quad\quad\text{pure}\circ\text{flm}\,f=f$ \textcolor{gray}{--
left identity}
\begin{itemize}
\item Empty context is preceded by a generator:
\end{itemize}
\texttt{\textcolor{blue}{\footnotesize{}}}%
\begin{minipage}[c][1\totalheight][t]{0.49\columnwidth}%
\begin{lyxcode}
\textcolor{blue}{\footnotesize{}x~$\leftarrow$~cont}{\footnotesize\par}

\textcolor{blue}{\footnotesize{}y~$\leftarrow$~pure(x)}{\footnotesize\par}
\end{lyxcode}
%
\end{minipage}\texttt{\textcolor{blue}{\footnotesize{}\hfill{}}}%
\begin{minipage}[c][1\totalheight][t]{0.49\columnwidth}%
\begin{lyxcode}
\textcolor{blue}{\footnotesize{}x~$\leftarrow$~cont}{\footnotesize\par}

\textcolor{blue}{\footnotesize{}y~=~x}{\footnotesize\par}
\end{lyxcode}
%
\end{minipage}\texttt{\textcolor{blue}{\footnotesize{}\hfill{}\medskip{}
cont.flatMap(x $\Rightarrow$ pure(x))}} \texttt{\textcolor{blue}{\footnotesize{}=
cont}} $\quad\quad\quad\text{flm}\left(\text{pure}\right)=\text{id}$
\textcolor{gray}{-- right identity}
\end{frame}

\begin{frame}{The monad laws formulated in terms of \texttt{\textcolor{blue}{\footnotesize{}pure}}
and \texttt{\textcolor{blue}{\footnotesize{}flatten}} }
\begin{itemize}
\item Naturality law for \texttt{\textcolor{blue}{\footnotesize{}pure}}:
$f\circ\text{pure}=\text{pure}\circ\text{fmap}\,f$
\[
\xymatrix{\xyScaleY{0.2pc}\xyScaleX{5pc} & B\ar[rd]\sp(0.5){\ \text{pure}^{\left[B\right]}}\\
A\ar[ru]\sp(0.5){f^{A\Rightarrow B}\ }\ar[rd]\sb(0.5){\text{pure}^{[A]}\,} &  & S^{B}\\
 & S^{A}\ar[ru]\sb(0.5){\text{fmap}\,f^{A\Rightarrow B}}
}
\]
\item Left identity: $\text{pure}\circ\text{flm}\,f=\text{pure}\circ\text{fmap}\,f\circ\text{ftn}=f\circ\text{pure}\circ\text{ftn}=f$
requires that $\text{pure}\circ\text{ftn}=\text{id}$ (both sides
applied to $S^{A}$)
\[
\xymatrix{\xyScaleY{0.2pc}\xyScaleX{3pc} & S^{S^{A}}\ar[rd]\sp(0.5){\ \text{ftn}^{[A]}\ }\\
S^{A}\ar[ru]\sp(0.5){\text{pure}^{[S^{A}]}\ }\ar[rr]\sb(0.5){\text{id}} &  & S^{A}
}
\]
\item Right identity: $\text{flm}\left(\text{pure}\right)=\text{fmap}\left(\text{pure}\right)\circ\text{ftn}=\text{id}^{S^{A}\Rightarrow S^{A}}$
\[
\xymatrix{\xyScaleY{0.2pc}\xyScaleX{3pc} & S^{S^{A}}\ar[rd]\sp(0.5){\ \text{ftn}^{[A]}\ }\\
S^{A}\ar[ru]\sp(0.5){\text{fmap}(\text{pure}^{[A]})\quad}\ar[rr]\sb(0.5){\text{id}} &  & S^{A}
}
\]
\end{itemize}
\end{frame}

\begin{frame}{Formulating laws via Kleisli functions}
\begin{itemize}
\item Recall: we formulated the laws of filterables via \texttt{\textcolor{blue}{\footnotesize{}fmapOpt}} 
\begin{itemize}
\item type signature of $\text{fmapOpt}:\left(A\Rightarrow1+B\right)\Rightarrow S^{A}\Rightarrow S^{B}$
\item and then we had to compose functions of types $A\Rightarrow1+B$ via
$\diamond_{\text{Opt}}$
\end{itemize}
\item Here we have{\small{} $\text{flm}:\left(A\Rightarrow S^{B}\right)\Rightarrow S^{A}\Rightarrow S^{B}$}
instead of \texttt{\textcolor{blue}{\footnotesize{}fmapOpt}} 
\item Can we compose \textbf{Kleisli functions} with ``twisted'' type,
$A\Rightarrow S^{B}$?
\item Use $\text{flm}$ to define \textbf{Kleisli composition}: $f^{A\Rightarrow S^{B}}\diamond g^{B\Rightarrow S^{C}}\equiv f\circ\text{flm}\,g$
\item Define \textbf{Kleisli identity} $\text{id}_{\diamond}$ of type $A\Rightarrow S^{A}$
as $\text{id}_{\diamond}\equiv\text{pure}$
\item Composition law: $\text{flm}\left(f\diamond g\right)=\text{flm}\,f\circ\text{flm}\,g$
(same as for \texttt{\textcolor{blue}{\footnotesize{}fmapOpt}})
\begin{itemize}
\item Shows that \texttt{\textcolor{blue}{\footnotesize{}flatMap}} is a
``lifting'' of $A\Rightarrow S^{B}$ to $S^{A}\Rightarrow S^{B}$
\end{itemize}
\item These laws are similar to functor ``lifting'' laws...
\begin{itemize}
\item except that $\diamond$ is used for composing Kleisli functions
\end{itemize}
\item What are the properties of $\diamond$?
\begin{itemize}
\item Exactly similar to the properties of function composition $f\circ g$
\end{itemize}
\end{itemize}
Reformulate $\text{flm}$'s laws in terms of the $\diamond$ operation:
\begin{itemize}
\item $\text{flm}$'s left and right identity laws: $\text{pure}\diamond f=f$
and $f\diamond\text{pure}=f$
\item Associativity law: $\left(f\diamond g\right)\diamond h=f\diamond\left(g\diamond h\right)$
\begin{itemize}
\item Follows from the $\text{flm}$ law: $f\circ\text{flm}\left(g\circ\text{flm}h\right)=f\circ\text{flm}\,g\circ\text{flm}\,h$
\end{itemize}
\end{itemize}
\end{frame}

\begin{frame}{{*} Motivation for categories and functors}

\framesubtitle{Compare different ``liftings'' seen so far, and generalize}
\begin{center}
\vspace{-0.25cm}%
\begin{tabular}{|c|c|c|c|}
\hline 
\textbf{Category} &
\textbf{Type }$A\rightsquigarrow B$ &
\textbf{Identity} &
\textbf{Composition}\tabularnewline
\hline 
\hline 
plain functions &
$A\Rightarrow B$ &
$\text{id}:A\Rightarrow A$ &
$f^{A\Rightarrow B}\circ g^{B\Rightarrow C}$\tabularnewline
\hline 
lifted to $F$ &
$F^{A}\Rightarrow F^{B}$ &
$\text{id}:F^{A}\Rightarrow F^{A}$ &
$f^{F^{A}\Rightarrow F^{B}}\circ g^{F^{B}\Rightarrow F^{C}}$\tabularnewline
\hline 
Kleisli over $F$ &
$A\Rightarrow F^{B}$ &
$\text{pure}:A\Rightarrow F^{A}$ &
$f^{A\Rightarrow F^{B}}\diamond g^{B\Rightarrow F^{C}}$\tabularnewline
\hline 
\end{tabular}
\par\end{center}

\vspace{-0.15cm}Category theory generalizes this situation

\textbf{Category}: a certain class of ``twisted functions'' $A\rightsquigarrow B$
called \textbf{morphisms}
\begin{itemize}
\item For any two morphisms $f^{A\rightsquigarrow B}$ and $g^{B\rightsquigarrow C}$
the \textbf{composition} morphism $f\diamond g$ of type $A\rightsquigarrow C$
must exist
\item For each type $A$, the \textbf{identity} morphism $\text{id}_{\diamond}$
of type $A\rightsquigarrow A$ must exist
\item Composition respects identity: $\text{id}_{\diamond}\diamond f=f$
and $f\diamond\text{id}_{\diamond}=f$
\item Composition is associative: $\left(f\diamond g\right)\diamond h=f\diamond\left(g\diamond h\right)$
\end{itemize}
General \textbf{functor}: a map from one category to another
\begin{itemize}
\item A functor must \texttt{\textcolor{blue}{\footnotesize{}fmap}} each
morphism from one category to the other
\item Functor laws: \texttt{\textcolor{blue}{\footnotesize{}fmap}} must
preserve identity and composition
\begin{itemize}
\item What we call ``functor'' is called \textbf{endofunctor} in category
theory
\item An endofunctor's \texttt{\textcolor{blue}{\footnotesize{}fmap}} goes
from plain functions to $F$-lifted functions
\end{itemize}
\end{itemize}
\end{frame}

\begin{frame}{{*} From Kleisli back to \texttt{\textcolor{blue}{\footnotesize{}flatMap}} }

The Kleisli functions, $A\rightsquigarrow B\equiv A\Rightarrow S^{B}$,
form a category iff $S$ is a monad 
\begin{itemize}
\item \texttt{\textcolor{blue}{\footnotesize{}fmap}} and \texttt{\textcolor{blue}{\footnotesize{}flatMap}}
are computationally equivalent to Kleisli composition:
\begin{itemize}
\item Define \texttt{\textcolor{blue}{\footnotesize{}flatMap}} through Kleisli:{\small{}
$\text{flm}\,f^{A\Rightarrow S^{B}}\equiv\text{id}^{S^{A}\Rightarrow S^{A}}\diamond f$}{\small\par}
\item Require two additional laws that connect $\diamond$, $\text{fmap}$,
and $\circ$:
\begin{itemize}
\item Left naturality: {\small{}$f^{A\Rightarrow B}\circ g^{B\Rightarrow S^{C}}=\left(f\circ\text{pure}\right)\diamond g$}{\small\par}
\item Right naturality: {\small{}$f^{A\Rightarrow S^{B}}\circ\text{fmap}\,g^{B\Rightarrow C}=f\diamond\left(g\circ\text{pure}\right)$}{\small\par}
\end{itemize}
\item So, can define \texttt{\textcolor{blue}{\footnotesize{}fmap}} through
Kleisli: $\text{fmap}\,g^{A\Rightarrow B}\equiv\text{id}^{S^{A}\Rightarrow S^{A}}\diamond\left(g\circ\text{pure}\right)$
\end{itemize}
\end{itemize}
The laws for \texttt{\textcolor{blue}{\footnotesize{}pure}} and \texttt{\textcolor{blue}{\footnotesize{}flatMap}}
then follow from category axioms for Kleisli:
\begin{itemize}
\item Left and right identity laws follow from $\text{id}\diamond\text{pure}=\text{id}$
and $\text{pure}\diamond f=f$ 
\item Associativity for \texttt{\textcolor{blue}{\footnotesize{}flatMap}}
follows from $\left(\text{id}\diamond f\right)\diamond g=\text{id}\diamond\left(f\diamond g\right)$
\item Use ``left naturality'', get: $\left(f\circ g\right)\diamond h=\left(f\circ pure\right)\diamond g\diamond h=f\circ\left(g\diamond h\right)$
\item Naturality for \texttt{\textcolor{blue}{\footnotesize{}pure}}: $\text{pure}\circ\text{fmap}\,f=\text{pure}\diamond\left(f\circ\text{pure}\right)=f\circ\text{pure}$
\item Define \texttt{\textcolor{blue}{\footnotesize{}flatten}}: $\text{ftn}=\text{id}^{S^{S^{A}}\Rightarrow S^{S^{A}}}\diamond\text{id}^{S^{A}\Rightarrow S^{A}}$
\item Naturality for \texttt{\textcolor{blue}{\footnotesize{}flatten}}:
$\text{ftn}\circ\text{fmap}\,f=\text{id}\diamond\text{id}\diamond\left(f\circ\text{pure}\right)=\text{id}\diamond\text{fmap}\,f$
and $\text{fmap}\left(\text{fmap}\,f\right)\circ\text{ftn}=\text{id}\diamond\left(\left(\text{fmap}\,f\right)\circ\text{pure}\right)\circ\text{id}\diamond\text{id}=\text{id}\diamond\text{fmap}\,f$
\end{itemize}
\end{frame}

\begin{frame}{Structure of semigroups and monoids}

\begin{itemize}
\item Semimonad contexts are combined associatively, as in a semigroup
\begin{itemize}
\item A full monad includes an ``empty'' context, i.e.\ the identity
element
\item Semigroup with an identity element is a monoid
\end{itemize}
\end{itemize}
Some constructions of semigroups and monoids (see code):
\begin{enumerate}
\item Any type $Z$ is a semigroup with operation $z_{1}\circledast z_{2}=z_{1}$
(or $z_{2}$)
\item $1+S$ is a monoid if $S$ is (at least) a semigroup (or $S\equiv0$)
\item $\text{List}^{A}$ is a monoid (for any type $A$), also $\text{Seq}^{A}$
etc.
\item The function type $A\Rightarrow A$ is a monoid (for any type $A$)
\begin{itemize}
\item The operation $f\circledast g$ can be either $f\circ g$ or $g\circ f$
\end{itemize}
\item Any totally ordered type is a monoid, with $\circledast$ defined
as $\max$ or $\min$
\item $S_{1}\times S_{2}$ is a semigroup (monoid) if $S_{1}$, $S_{2}$
are semigroups (monoids)
\item $S_{1}+S_{2}$ is a semigroup (monoid) if $S_{1}$, $S_{2}$ are semigroups
(monoids)
\item \texttt{\textcolor{blue}{\footnotesize{}M{[}S{]}}} is a monoid if
\texttt{\textcolor{blue}{\footnotesize{}M{[}\_{]}}} is a monad and
\texttt{\textcolor{blue}{\footnotesize{}S}} is a monoid
\item $S\times P$ is a semigroup if $S$ is a semigroup that has an \textbf{action
on} $P$
\begin{itemize}
\item The ``action'' is $\alpha:S\Rightarrow P\Rightarrow P$ such that
$\alpha(s_{2})\circ\alpha(s_{1})=\alpha(s_{1}\circledast s_{2})$
\item $S\times P$ is a ``twisted product.'' Examples: $\left(A\Rightarrow A\right)\times A$;
$\text{Bool}\times\left(1+A\right)$
\end{itemize}
\end{enumerate}
\begin{itemize}
\item Other examples of monoids: $\text{Int}$ (many), $\text{String}$,
$\text{Set}^{A}$, Akka's \texttt{\textcolor{blue}{\footnotesize{}Route}} 
\end{itemize}
\end{frame}

\begin{frame}{Structure of (semi)monads}


\framesubtitle{How to recognize a (semi)monad by its type? Open question!}

Intuition from \texttt{\textcolor{blue}{\footnotesize{}flatten}}:
reshuffle data in $F^{F^{A}}$ to fit into $F^{A}$

Some constructions of exponential-polynomial (semi)monads:
\begin{enumerate}
\item $F^{A}\equiv Z$ (constant functor) for a fixed type $Z$
\begin{itemize}
\item For a full monad, need to choose $Z=1$ 
\end{itemize}
\item $F^{A}\equiv A\times G^{A}$ for any functor $G^{A}$ (a full monad
only if $G^{A}$ is a monad)
\item $F^{A}\equiv G^{A}\times H^{A}$ for any (semi)monads $G^{A}$ and
$H^{A}$
\begin{itemize}
\item but $G^{A}+H^{A}$ is generally \emph{not} a semimonad
\end{itemize}
\item $F^{A}\equiv R\Rightarrow G^{A}$ is a (semi)monad for any (semi)monad
$G^{A}$
\item $F^{A}\equiv A+G^{A}$ is a monad for a monad $G^{A}$ (\textbf{free
pointed} over $G$)
\item $F^{A}\equiv G^{Z+A\times W}$ is a monad if $G$ is a monad and $W$
a monoid
\item $F^{A}\equiv A+G^{F^{A}}$ (recursive) for any functor $G^{A}$ (\textbf{free
monad} over $G$)

\emph{Semimonad-only} constructions:
\item $F^{A}\equiv G^{A}+G^{F^{A}}$ (recursive) for any functor $G^{A}$
\item $F^{A}\equiv H^{A}\Rightarrow A\times G^{A}$ for any contrafunctor
$H^{A}$ and functor $G^{A}$
\begin{itemize}
\item Obtain a full monad only when $G^{A}\equiv1$, i.e.\ $F^{A}\equiv H^{A}\Rightarrow A$
\end{itemize}
\end{enumerate}
\end{frame}

\begin{frame}{Exercises II}
\begin{enumerate}
\item \vspace*{-0.2cm}Show that \texttt{\textcolor{blue}{\footnotesize{}M{[}S{]}}}
is a monoid if \texttt{\textcolor{blue}{\footnotesize{}M{[}\_{]}}}
is a monad and \texttt{\textcolor{blue}{\footnotesize{}S}} is a monoid.
\item A framework implements a ``route'' type $R$ as $R\equiv Q\Rightarrow\left(E+S\right)$,
where $Q$ is a query, $E$ is an error response, and $S$ is a success
response. A server is defined as a ``sum'' of several routes. For
a given query $Q$, the response is the first route (if it exists)
that yields a success. Implement the route ``summation'' operation
and show that it makes $R$ into a semigroup. What would be necessary
to make $R$ into a monoid?
\item Verify the associativity law for the semimonad $F^{A}\equiv Z+\text{Bool}\times A$.
\item Show that the functor $F^{A}\equiv\text{Boolean}\times M^{A}$ (where
$M^{A}$ is an arbitrary monad) can be made into a semimonad but not
into a monad.
\item If $W$ and $R$ are arbitrary fixed types, which of the functors
can be made into a semimonad: $F^{A}\equiv W\times\left(R\Rightarrow A\right)$,
$G^{A}=R\Rightarrow\left(W\times A\right)$?
\item Show that $F^{A}\equiv\left(P\Rightarrow A\right)+\left(Q\Rightarrow A\right)$
is not a semimonad (cannot define \texttt{\textcolor{blue}{\footnotesize{}flatMap}})
when $P$ and $Q$ are arbitrary, different types.
\item Implement the \texttt{\textcolor{blue}{\footnotesize{}flatten}} and
\texttt{\textcolor{blue}{\footnotesize{}pure}} methods for $D^{A}\equiv1+A\times A$
(\texttt{\textcolor{blue}{\footnotesize{}type D{[}A{]} = Option{[}(A,
A){]}}}) in at least two significantly different ways, and show that
the monad laws always fail to hold. ($D^{A}$ is not a monad!)
\end{enumerate}
\end{frame}

\begin{frame}{Exercises II (continued)}
\begin{enumerate}
\item []\addtocounter{enumi}{7}\vspace*{-0.5cm}
\item A programmer implemented the \texttt{\textcolor{blue}{\footnotesize{}fmap}}
method for {\footnotesize{}$F^{A}\equiv A\times\left(A\Rightarrow Z\right)$
}as
\begin{lyxcode}
\textcolor{blue}{\footnotesize{}def~fmap{[}A,B{]}(f:~A$\Rightarrow$B):~((A,~A$\Rightarrow$Z))~$\Rightarrow$~(B,~B$\Rightarrow$Z)~=}{\footnotesize\par}

\textcolor{blue}{\footnotesize{}~~\{~case~(a,~az)~$\Rightarrow$~(f(a),~(\_:~B)~$\Rightarrow$~az(a))~\}}{\footnotesize\par}
\end{lyxcode}
Show that this implementation fails to satisfy the functor laws.
\item Show that $P^{A}\equiv Z+W\times A$ is a (full) monad if $W$ is
a monoid.
\item Verify that the full monad laws hold for construction 4.
\item Implement \texttt{\textcolor{blue}{\footnotesize{}flatten}} and \texttt{\textcolor{blue}{\footnotesize{}pure}}
for $F^{A}\equiv A+\left(R\Rightarrow A\right)$, where $R$ is a
fixed type, and show that all the monad laws hold.
\item For construction 5, show that an identity law would fail if \texttt{\textcolor{blue}{\footnotesize{}pure}}
were defined as \texttt{\textcolor{blue}{\footnotesize{}a $\Rightarrow$
Right(Monad{[}G{]}.pure(a))}} instead of as \texttt{\textcolor{blue}{\footnotesize{}Left(a)}}.
\item Implement the monad methods for $F^{A}\equiv\left(Z\Rightarrow1+A\right)\times\text{List}^{A}$
using the known monad constructions (no need to check the laws).
\item Implement the semimonad construction 2 by discarding the first effect
(not the second), and show that the associativity law is still satisfied.
\item For semimonad construction 8, show that the associativity law holds.
\item Verify the identity laws for the State and Continuation monads.
\end{enumerate}
\end{frame}

\begin{frame}{Addendum: Miscellaneous remarks on monads}
\begin{itemize}
\item {\footnotesize{}\vspace{-0.2cm}A non-empty list $F^{A}\equiv A\times\text{List}^{A}$
is a semigroup but not a monoid.}{\footnotesize\par}
\item {\footnotesize{}Any polynomial functor $F^{A}\equiv p(A)$ can be
made into a monad when $p(x)$ is a polynomial of the form $p(x)=x^{n_{1}}+x^{n_{2}}+...+x^{n_{k}}$
for some }\emph{\footnotesize{}positive}{\footnotesize{} integers
$n_{1}$, ..., $n_{k}$. Indeed, any $F^{A}$ of this form may be
built from the identity monad via constructions 3 and 5. To illustrate
this, denote $E_{1}\equiv1$, $E_{n+1}\equiv1+E_{n}$. Monoid construction
2 makes $E_{n}$ into monoids. Then the monads $E_{n}\Rightarrow A$
(reader) and $E_{n}\times A$ (writer) are equivalent to polynomial
monads $A\times...\times A$ and $A+...+A$.}{\footnotesize\par}
\item {\footnotesize{}Contrafunctors cannot be monads or semimonads: if
$H^{A}$ is a contrafunctor then $H^{H^{A}}$ is a }\emph{\footnotesize{}functor}{\footnotesize{},
so a natural transformation between $H^{H^{A}}$ and $H^{A}$ (in
either direction) is impossible.}{\footnotesize\par}
\item {\footnotesize{}An example of combining natural transformations: Given
functors $C$, $F$, $G$ and natural transformations $C^{A}\Rightarrow F^{A}$
and $C^{A}\Rightarrow G^{A}$ and taking the product, we get a natural
transformation $C^{A}\Rightarrow F^{A}\times G^{A}$. }{\footnotesize\par}
\item {\footnotesize{}If $M^{A}$ is a monad then $M^{M^{A}}$ is not automatically
a monad (need counterexample?).}{\footnotesize\par}
\item {\footnotesize{}Two monadic values $m_{1},m_{2}:M^{A}$ can be merged
by ignoring the payload of one of them and merging the effects; and
we can merge the effects in any chosen order: }\texttt{\textcolor{blue}{\footnotesize{}for
\{ x $\leftarrow$ m$_{1}$; \_ $\leftarrow$ m$_{2}$ \} yield x}}{\footnotesize{}
or }\texttt{\textcolor{blue}{\footnotesize{}for \{ \_ $\leftarrow$
m$_{1}$; x $\leftarrow$ m$_{2}$ \} yield x}} 
\item {\footnotesize{}A curious example: The functor $Q^{A}\equiv\left(A\Rightarrow Z\right)\Rightarrow1+A$
is not a monad (and not even a lawful applicative) but $M^{A}\equiv\left(A\Rightarrow1+1\right)\Rightarrow1+A$
is a ``search monad''. More generally, a ``selector monad'' is
$\left(A\Rightarrow P^{1}\right)\Rightarrow P^{A}$ for any functor
$P^{A}$.}{\footnotesize\par}
\end{itemize}
\end{frame}

\end{document}
tesize\par}
\end{itemize}
\end{frame}

\end{document}
